Modern distributed computer systems are typically composed of a number of independently operating nodes. A node can be a processor, memory, a circuit board, a server, a storage server, a core or a multicore processor, an external network connection or any other data processing, storing, or transmitting device. It is often the case that these independently operating nodes need access to the same resource. For example, two nodes may need to use an output port of another node for transmitting information or need to use a shared resource such as a shared communication bus. Without coordination, these two nodes may begin to simultaneously use the resource. It may be the case that the information sent by one or both of the nodes is lost or corrupted upon arrival at the resource. Thus, computer systems often employ a conflict resolution scheme called “arbitration” in order to prevent two or more nodes from simultaneously using the same resource. Arbitration ensures that only one node at a time uses the resource.
In many cases, arbitration lies on the critical path of computer system performance since arbitration inherently sequences two or more otherwise independent parallel activities. The nodes requesting access to a resource can be physically distributed. A typical arbitration scheme involves communication to gather all the “requests” for the resource, a centralized or distributed computation to select or “grant” one of the requests, and then an additional communication is needed to distribute the “grant” to the node which has won the arbitration.
The most critical property of any arbitration mechanism is the ability to grant access to at most one requesting node at any given time. This arbitration property is typically called “mutual exclusion.” Fairness is another property that is necessary to make an arbitration mechanism useful in practice. In general, fairness implies that competing requests will win arbitration with equal probability given a sufficiently large enough sample of competing nodes. While this general interpretation of fairness is often considered ideal, it is often expensive to achieve in practice. This is particularly true for distributed arbitration schemes where the overhead incurred to achieve this general notion of fairness often results in reduced performance and increased cost. The overhead problem becomes particularly impractical if cost and performance become significantly worse as the system size increases. This “scaling” issue is particularly important for arbitration mechanisms which are intended for use in systems comprising a large number of nodes.
It is possible to relax this general notion of arbitration fairness to a policy in order to provide “starvation free” arbitration. When arbitration is starvation free, it guarantees that any requesting node will eventually win the arbitration. While starvation free arbitration usually incurs less overhead and has improved scaling properties when compared to truly fair arbitration, it is problematic in that it inherently treats all requests at any given point in time as having equal priority. In general, overall system performance is degraded significantly if certain requests are delayed to the point where ungranted requests become performance bottlenecks. In any system, some requests have higher priority than others. Priority based arbitration implies that higher priority requests will be granted prior to lower priority requests. In priority based schemes, each new request is assigned an initial priority based on some importance metric. An additional option is to allow priorities to be increased based on how long they have been waiting to win arbitration access to a particular resource. This “age based arbitration priority” can be coupled with starvation free arbitration at each priority level to achieve an arbitration policy with reasonable fairness, scaling, and cost properties.
Any correct arbitration mechanism must be capable of guaranteeing mutually exclusive access to a shared resource, and must do so in a way that is starvation free. Other desirable properties of an arbitration mechanism include scalability in terms of cost and performance. The key to cost scalability is minimizing the physical resources, such as energy, wires, waveguides, and transistors, required to implement the arbitration policy, and the key to performance scalability is the need to reduce the latency of an individual arbitration decision as much as possible. Engineers and computer scientists continue to develop lower latency arbitration systems and methods to increase system performance.